//
//  LinkList.hpp
//  LinkList
//
//  Created by chenyh on 2021/2/4.
//

#ifndef LinkList_hpp
#define LinkList_hpp

#include <iostream>

template <typename DataType> class ListNode;

template <typename DataType> class LinkList
{
public:
    //无参数构造函数
    LinkList()
    {
        head = new ListNode<DataType>();
    }
    //有参数构造函数
    LinkList(ListNode<DataType> *node)
    {
        head = node;
    };
    //析构函数
    ~LinkList()
    {
        delete head;
    }
    //插入结点到某个结点的后面
    bool insertNode(int i,DataType newData);
    //插入结点到表尾
    bool insertNode(ListNode<DataType> *q,DataType newData);
    
    bool insertNode(DataType newData);
    //删除结点
    bool removeNode(ListNode<DataType> *q);
    //查找指定值的结点并返回地址
    ListNode<DataType>* findNode(DataType value);
    //清空链表
    bool cleanLink();
    //获取结点数据
    DataType getNodeData(ListNode<DataType> *p);
private:
    ListNode<DataType> *head;
};

//定义链表结点
template <typename DataType> class ListNode {
public:
    ListNode()
    {
        next = NULL;
    }
    ListNode(DataType item,ListNode<DataType> *nextNode = NULL)
    {
        data = item;
        next = nextNode;
    }
    ~ListNode()
    {
        next = NULL;
    }
    //获取结点内的数据
    DataType getData()
    {
        return data;
    }
    //获取指针域
    ListNode* getNext()
    {
        return next;
    }
private:
    //将linklist设为友元类，方便其对node的成员数据和方法进行访问
    friend  typename  LinkList<DataType>::head;
    DataType *next;     //只想下一个结点的指针
    DataType  data;     //结点中的数据
};



template <typename DataType>
bool LinkList<DataType>:: insertNode(int i,DataType newData) {
    ListNode<DataType> *p = head;   //设置游标指针，初始化为头结点地址
    int j;
    for (j=1; j<i-1; j++) {
        p = p->next;
        if (p == NULL) { //如果指针为空，则不存在该结点，或已倒末尾
            break;
        }
    }
    if (p==NULL && j < (i-1)) {//指针为空且没有到第i个位置，说命不存在第i个结点
        std::cout<<"插入位置无效! "<<std::endl;
        return false;
    }
    //建立新结点
    ListNode<DataType> *node = new ListNode<DataType>(newData);
    //将node的next指针赋值为p的后继结点地址
    node->next = p->next;
    //p的后继指针指向node
    p->next = node;
    return true;
}

template <typename DataType>
bool LinkList<DataType>:: insertNode(DataType newData)
{
    ListNode<DataType> *p = head;
    ListNode<DataType> *node = new ListNode<DataType>(newData);
    if (node == NULL) {
        return false;
    }
    while (p->next != NULL) { //遍历单链表，找到尾结点
        p = p->next;
    }
    p->next = node; //将尾结点next指针指向新结点；
    return true;
}
template <typename DataType>
bool LinkList<DataType>:: removeNode(ListNode<DataType> *q)
{
    if (q == NULL) { //判断待删除节点是否存在
        std::cout<<"待删除节点不存在！"<<std::endl;
        return false;
    }
    ListNode<DataType> *ptemp = head;
    while (ptemp->next != q) { //遍历单链表，找到q所指向结点的前驱结点
        ptemp = ptemp->next;
    }
    ptemp->next = q->next; //将q结点的后继结点地址复制给其前驱结点
    delete q;  //回收结点q的空间
    return true;
    
}

template <typename DataType>
ListNode<DataType> * LinkList<DataType>:: findNode(DataType value)
{
    ListNode<DataType> *currentPointer = head;//设置游标结点
    //p判断游标指针所指结点的值是否与value相等
    while (currentPointer != NULL && currentPointer->data != value) {
        currentPointer = currentPointer->next;
    }
    if (currentPointer == NULL) {
        std::cout<<"咩有找到该结点！程序异常退出"<<std::endl;
        exp(1);
    }
    else
    {
        return currentPointer;//返回所找到的结点的指针
    }
}
template <typename DataType>
bool LinkList<DataType>:: cleanLink()
{
    ListNode<DataType> *currentPointer = head;//设置游标结点
    while (currentPointer->next != NULL) {
        currentPointer = head->next;    //将current指向head的后继结点
        head->next = currentPointer->next; //将curennt的后记地址复制给head的next域
        delete currentPointer; //回收current结点所占的空间
    }
}
#endif /* LinkList_hpp */
